package hanjia;

import suanfa.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/4-下午10:01
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode23 {

    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }


        if (list1.val < list2.val) {
            list1.next = mergeTwoLists2(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists2(list1, list2.next);
            return list2;
        }


    }

    public ListNode mergeKLists(ListNode[] lists) {

         return  spilt(lists, 0, lists.length - 1);


    }

    public ListNode spilt(ListNode[] lists, int left, int right) {
        if (left==right){
            return lists[left];
        }

        int mid = (left + right) >>> 1;
        ListNode leftNode = spilt(lists, left, mid);
        ListNode rightNode= spilt(lists, mid + 1, right);
        return mergeTwoLists2(leftNode,rightNode);

    }

    public ListNode mergeKLists2(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((a,b)->a.val-b.val);
        for (ListNode listNode:lists){
            if (listNode!=null){
                priorityQueue.offer(listNode);
            }

        }
        ListNode result = new ListNode();
        ListNode temp=result;
        while (!priorityQueue.isEmpty()){

            ListNode poll = priorityQueue.poll();
            temp.next=poll;
            temp=temp.next;
            if (poll.next!=null){
                priorityQueue.offer(poll.next);
            }

        }
        return result.next;


    }



}
